package com.ztom.hard;

import java.util.Deque;
import java.util.LinkedList;

/**
 * 滑动窗口的最大值
 * <p>
 * https://leetcode-cn.com/problems/hua-dong-chuang-kou-de-zui-da-zhi-lcof/
 *
 * @author ZhangTao
 */
public class Code06MaxSlidingWindow {

    public int[] maxSlidingWindow1(int[] nums, int k) {
        if (nums == null || nums.length == 0) {
            return new int[]{};
        }

        int n = nums.length;
        int[] res = new int[n - k + 1];

        // 存的是角标
        Deque<Integer> qMax = new LinkedList<>();
        int index = 0;
        for (int i = 0; i < n; i++) {
            while (!qMax.isEmpty() && nums[qMax.peekLast()] <= nums[i]) {
                qMax.pollLast();
            }
            qMax.offerLast(i);
            // 过期
            if (i - qMax.peekFirst() >= k) {
                qMax.pollFirst();
            }
            // 形成窗口
            if (i + 1 >= k) {
                res[index++] = nums[qMax.peekFirst()];
            }
        }

        return res;
    }

    /**
     * 数组优化队列
     */
    public int[] maxSlidingWindow(int[] nums, int k) {
        if (nums == null || nums.length == 0) {
            return new int[]{};
        }

        int n = nums.length;
        int[] res = new int[n - k + 1];

        // 存的是角标
        int[] qMax = new int[n + 1];
        // 数组模拟队列
        int head = 0;
        int tail = -1;
        int index = 0;
        for (int i = 0; i < n; i++) {
            // head <= tail 说明队列不为空
            while (head <= tail && nums[qMax[tail]] <= nums[i]) {
                // 队尾移除
                tail--;
            }
            qMax[++tail] = i;
            // 过期
            if (head <= tail && i - qMax[head] >= k) {
                head++;
            }
            // 形成窗口
            if (i + 1 >= k) {
                res[index++] = nums[qMax[head]];
            }
        }

        return res;
    }
}
